package com.zdp.leetcode;

import com.zdp.util.ListNode;

/*
* 题目描述：
* 反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 反转链表 {
    ListNode result = null;
    //迭代法反转链表
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        while(head!=null){
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
    //递归反转链表
    public ListNode reverseList1(ListNode head) {
        if(head==null)
            return null;
        ListNode r = f(head);
        r.next = null;
       return result;
    }
    public ListNode f(ListNode p){
        if(p.next == null){
            this.result = p;
            return p;
        }
        ListNode r = f(p.next);
        r.next = p;
        return p;
    }
    //官方给的递归解
    public ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = reverseList2(head.next); //反转后的头结点
        head.next.next = head; // 当前结点的下一个结点指向 当前结点
        head.next = null; //当前结点指向空
        return p;
    }

}

